package data.structure.heap;

/**
 * 最小堆粗糙实现，有待优化
 * @author xuyuji
 *
 */
public class MinHeap {

	private int[] array;
	
	private int capacity;
	
	private int size;
	
	private int depth;
	
	public MinHeap(int capacity) {
		this.array = new int[capacity];
		this.capacity = capacity;
		this.size = 0;
		
		this.depth = 0;
		int i = 1;
		while(i <= capacity){
			depth += 1;
			i <<= 1;
		}
	}
	
	public void add(int e){
		if(size < capacity){
			array[size++] = e;
			rise(size);
		}else{
			int max = (int) Math.pow(2, depth - 1);
			for(int i = max + 1; i < capacity + 1; i++){
				if(array[max - 1] < array[i - 1]){
					max = i;
				}
			}
			
			if(e < array[max - 1]){
				array[max - 1] = e;
				rise(max);
			}
		}
	}
	
	private void rise(int i){
		int parent = parent(i);
		if(parent == 0){
			return;
		}
		
		if(array[i - 1] < array[parent - 1]){
			swap(i - 1, parent - 1);
			rise(parent);
		}
	}
	
	private void swap(int i, int j){
		int t = array[i];
		array[i] = array[j];
		array[j] = t;
	}
	
	private void sink(int i){
		int left = left(i);
		int right = right(i);
		if(left > size){
			return;
		}
		if(right > size){
			right = left;
		}
		
		int minChild;
		if(array[left - 1] < array[right - 1]){
			minChild = left;
		}else{
			minChild = right;
		}
		
		if(array[i - 1] > array[minChild - 1]){
			swap(i - 1, minChild - 1);
			sink(minChild);
		}
	}
	
	public int takeRoot(){
		int root = array[0];
		array[0] = array[size - 1];
		size -= 1;
		sink(1);
		return root;
	}
	
	private int parent(int i){
		return i / 2;
	}
	
	private int left(int i){
		return i * 2;
	}
	
	private int right(int i){
		return i * 2 + 1;
	}
	
	public static void main(String[] args) {
		MinHeap minHeap = new MinHeap(10);
		minHeap.add(4);
		minHeap.add(12);
		minHeap.add(11);
		minHeap.add(41);
		minHeap.add(13);
		minHeap.add(1);
		minHeap.add(2);
		minHeap.add(3);
		minHeap.add(5);
		minHeap.add(6);
		minHeap.add(7);
		minHeap.add(8);
		minHeap.add(9);
		
		System.out.println(minHeap);
		System.out.println(minHeap.takeRoot());
		System.out.println(minHeap);
		System.out.println(minHeap.takeRoot());
		System.out.println(minHeap);
		
		minHeap.add(2);
		System.out.println(minHeap);
		
		minHeap = new MinHeap(10);
		minHeap.add(4);
		minHeap.add(12);
		minHeap.add(11);
		minHeap.add(41);
		minHeap.add(13);
		minHeap.add(1);
		minHeap.add(2);
		minHeap.add(3);
		minHeap.add(5);
		minHeap.add(6);
		minHeap.add(7);
		minHeap.add(8);
		
		System.out.println(minHeap);
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < size; i++){
			sb.append(array[i]).append(",");
		}
		return sb.toString();
	}
}